SherbyNet - /page/wikibook/entry.mu

Micron Document

Logarithmically concave function

19.1 KB · ⇊ 12 parts · ⤓ Micron 19.1 KB · ⤓ HTML 45.4 KB

──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

top

In convex analysis, a non-negative function f : Rn → R+ is logarithmically concave (or log-concave for short) if its domain is a convex set, and if it satisfies the inequality

f ( θ θ x + ( 1 − − θ θ ) y ) ≥ ≥ f ( x ) θ θ f ( y ) 1 − − θ θ {\displaystyle f(\theta x+(1-\theta )y)\geq f(x)^{\theta }f(y)^{1-\theta }}

for all x,y ∈ dom f and 0 < θ < 1. If f is strictly positive, this is equivalent to saying that the logarithm of the function, log ∘ f, is concave; that is,

log ⁡ ⁡ f ( θ θ x + ( 1 − − θ θ ) y ) ≥ ≥ θ θ log ⁡ ⁡ f ( x ) + ( 1 − − θ θ ) log ⁡ ⁡ f ( y ) {\displaystyle \log f(\theta x+(1-\theta )y)\geq \theta \log f(x)+(1-\theta )\log f(y)}

for all x,y ∈ dom f and 0 < θ < 1.

Examples of log-concave functions are the 0-1 indicator functions of convex sets (which requires the more flexible definition), and the Gaussian function.

Similarly, a function is log-convex if it satisfies the reverse inequality

f ( θ θ x + ( 1 − − θ θ ) y ) ≤ ≤ f ( x ) θ θ f ( y ) 1 − − θ θ {\displaystyle f(\theta x+(1-\theta )y)\leq f(x)^{\theta }f(y)^{1-\theta }}

for all x,y ∈ dom f and 0 < θ < 1.

Contents

• Properties

• Operations preserving log-concavity

• Log-concave distributions

• See also

• Notes

• References

Properties

• A log-concave function is also quasi-concave. This follows from the fact that the logarithm is monotone implying that the superlevel sets of this function are convex.cite-ref-0-1-0[1]

• Every concave function that is nonnegative on its domain is log-concave. However, the reverse does not necessarily hold. An example is the Gaussian function f(x) = exp(−x2/2) which is log-concave since log f(x) = −x2/2 is a concave function of x. But f is not concave since the second derivative is positive for |x| > 1:

f ″ ( x ) = e − − x 2 2 ( x 2 − − 1 ) ≰ ≰ 0 {\displaystyle f''(x)=e^{-{\frac {x^{2}}{2}}}(x^{2}-1)\nleq 0}

• From above two points, concavity ⇒ ⇒ {\displaystyle \Rightarrow } log-concavity ⇒ ⇒ {\displaystyle \Rightarrow } quasiconcavity.

• A twice differentiable, nonnegative function with a convex domain is log-concave if and only if for all x satisfying f(x) > 0,

f ( x ) ∇ ∇ 2 f ( x ) ⪯ ⪯ ∇ ∇ f ( x ) ∇ ∇ f ( x ) T {\displaystyle f(x)\nabla ^{2}f(x)\preceq \nabla f(x)\nabla f(x)^{T}} ,cite-ref-0-1-1[1]

i.e.

f ( x ) ∇ ∇ 2 f ( x ) − − ∇ ∇ f ( x ) ∇ ∇ f ( x ) T {\displaystyle f(x)\nabla ^{2}f(x)-\nabla f(x)\nabla f(x)^{T}} is

negative semi-definite. For functions of one variable, this condition simplifies to

f ( x ) f ″ ( x ) ≤ ≤ ( f ′ ( x ) ) 2 {\displaystyle f(x)f''(x)\leq (f'(x))^{2}}

Operations preserving log-concavity

• Products: The product of log-concave functions is also log-concave. Indeed, if f and g are log-concave functions, then log f and log g are concave by definition. Therefore

log f ( x ) + log g ( x ) = log ⁡ ⁡ ( f ( x ) g ( x ) ) {\displaystyle \log \,f(x)+\log \,g(x)=\log(f(x)g(x))}

is concave, and hence also f g is log-concave.

• Marginals: if f(x,y) : Rn+m → R is log-concave, then

g ( x ) = ∫ ∫ f ( x , y ) d y {\displaystyle g(x)=\int f(x,y)dy}

is log-concave (see Prékopa–Leindler inequality).

• This implies that convolution preserves log-concavity, since h(x,y) = f(x-y) g(y) is log-concave if f and g are log-concave, and therefore

( f ∗ ∗ g ) ( x ) = ∫ ∫ f ( x − − y ) g ( y ) d y = ∫ ∫ h ( x , y ) d y {\displaystyle (f*g)(x)=\int f(x-y)g(y)dy=\int h(x,y)dy}

is log-concave.

Log-concave distributions

Log-concave distributions are necessary for a number of algorithms, e.g. adaptive rejection sampling. Every distribution with log-concave density is a maximum entropy probability distribution with specified mean μ and Deviation risk measure D.cite-ref-grechuk1-2-0[2] As it happens, many common probability distributions are log-concave. Some examples:cite-ref-1-3-0[3]

• the normal distribution and multivariate normal distributions,

• the exponential distribution,

• the uniform distribution over any convex set,

• the binomial distribution,

• the logistic distribution,

• the extreme value distribution,

• the Laplace distribution,

• the chi distribution,

• the hyperbolic secant distribution,

• the Wishart distribution, if n ≥ p + 1,cite-ref-prekopa-4-0[4]

• the Dirichlet distribution, if all parameters are ≥ 1,cite-ref-prekopa-4-1[4]

• the gamma distribution if the shape parameter is ≥ 1,

• the chi-square distribution if the number of degrees of freedom is ≥ 2,

• the beta distribution if both shape parameters are ≥ 1, and

• the Weibull distribution if the shape parameter is ≥ 1.

Note that all of the parameter restrictions have the same basic source: The exponent of non-negative quantity must be non-negative in order for the function to be log-concave.

The following distributions are non-log-concave for all parameters:

• the Student's t-distribution,

• the Cauchy distribution,

• the Pareto distribution,

• the log-normal distribution, and

• the F-distribution.

Note that the cumulative distribution function (CDF) of all log-concave distributions is also log-concave. However, some non-log-concave distributions also have log-concave CDF's:

• the log-normal distribution,

• the Pareto distribution,

• the Weibull distribution when the shape parameter < 1, and

• the gamma distribution when the shape parameter < 1.

The following are among the properties of log-concave distributions:

• If a density is log-concave, so is its cumulative distribution function (CDF).

• If a multivariate density is log-concave, so is the marginal density over any subset of variables.

• The sum of two independent log-concave random variables is log-concave. This follows from the fact that the convolution of two log-concave functions is log-concave.

• The product of two log-concave functions is log-concave. This means that joint densities formed by multiplying two probability densities (e.g. the normal-gamma distribution, which always has a shape parameter ≥ 1) will be log-concave. This property is heavily used in general-purpose Gibbs sampling programs such as BUGS and JAGS, which are thereby able to use adaptive rejection sampling over a wide variety of conditional distributions derived from the product of other distributions.

• If a density is log-concave, so is its survival function.cite-ref-1-3-1[3]

• If a density is log-concave, it has a monotone hazard rate (MHR), and is a regular distribution since the derivative of the logarithm of the survival function is the negative hazard rate, and by concavity is monotone i.e.

d d x log ⁡ ⁡ ( 1 − − F ( x ) ) = − − f ( x ) 1 − − F ( x ) {\displaystyle {\frac {d}{dx}}\log \left(1-F(x)\right)=-{\frac {f(x)}{1-F(x)}}} which is decreasing as it is the derivative of a concave function.